1. Field of the Invention
The present invention relates to a low density parity check (LDPC) coding method, and more particularly, to a method of executing LDPC coding using a parity check matrix.
2. Discussion of the Related Art
FIG. 1 is a block diagram of a structure of a mobile communication channel to which a related art or the present invention is applicable. A structure of a mobile communication channel is explained with reference to FIG. 1 as follows.
Referring to FIG. 1, a transmitter undergoes channel coding to transmit data on a wireless channel without loss or distortion. The channel coding includes various schemes such as convolutional coding, turbo coding, LDPC coding, and the like. Data through the channel coding can be transmitted as a single symbol on a wireless channel in a manner that a plurality of bits gather to form the single symbol. In doing so, a procedure for mapping a plurality of bits to a single symbol is called modulation.
The modulated data is transformed into a signal for multiplexed transmission via a multiplexing or multiple access. The multiplexing scheme includes one of various schemes such as CDM, TDM, FDM, and the like. A signal via the multiplexing block is modified to have a structure suitable for being transmitted via multi-antenna and is then delivered to a receiver via a wireless channel. The transmitted data undergoes fading and thermal noise in the course of being carried through the wireless channel. So, the transmitted data may be distorted.
The modulated data is delivered to the receiver via the wireless channel. In this process, the transmitted experiences fading and thermal noise to have distortion possibly. Having received the distorted data, the receiver executes a series of procedures in order reverse to those of the transmitter. In particular, demodulation for transforming the data mapped to the symbol into a bit sequence is carried out. Channel decoding is then executed to reconstruct the distorted data into original data.
A device for performing the channel coding stores a matrix H, which is a parity check matrix for generating parity bits to be added to inputted data (information bits or systematic bits), or a generation matrix (matrix-G) derived from the matrix H therein. Namely, the transmitter includes an encoder that generates parity bits via the matrix-H or the matrix-G and the inputted data. A channel decoding device checks whether the inputted data (systematic bits) are correctly reconstructed or not via the matrix H and logical operations for the received data (distorted systematic bits+parity bits). If the reconstruction fails, the logical operations are re-executed.
The modulation includes one of BPSK (binary phase sift keying), QPSK (quadrature phase shift keying), 16-QAM (quadrature amplitude modulation), 64-QAM, 256-QAM, and the like. For instance, in case of performing modulation, 16-QAM maps a data sequence, which undergoes a channel encoding procedure, to a single symbol by a 4-bit unit. In case of performing demodulation, 16-QAM de-maps a single symbol of data received via a wireless channel to four bits. Data retransmission scheme applicable to the present invention is explained as follows. There are various kinds of data retransmission schemes. Particularly, HARQ (hybrid automatic repeat request) scheme is explained.
First of all, HARQ is the scheme generated from combining a retransmission scheme ARQ (automatic repeat request) with FEC (forward error correction) code. The ARQ is the scheme that a receiver makes a request for retransmission from a transmitter if error is detected from data received by the receiver. The ARQ scheme can be categorized into Stop-And-Wait, Selective Repeat, Go-Back-N, and the like in accordance with a retransmission technique.
Referring to FIG. 2, in the Stop-And-Wait scheme, a transmitter transmits data and then receives an acknowledgement (ACK) message announcing that a receiver successfully has received the data. If so, the transmitter transmits next data. In case of receiving a NACK message announcing that the data was not successfully received by the receiver, the transmitter retransmits the corresponding data.
In the Go-Back-N scheme, a transmitter sends N data first and then receives ACK messages in turn from a receiver. FIG. 3 shows a case that N is 7. In this case, the number (N) of data sent without receiving ACK is called a window size. In case of receiving a NACK message for a kth data, the transmitter sequentially transmits data from the kth data.
FIG. 4 shows the Selective Repeat scheme. In the Selective Repeat scheme, like the Go-Back-N scheme, data is transmitted by setting a window size to N without receiving ACK or NACK message. And, retransmission is selectively carried out on the data of which NACK message has been received only.
In the above-explained HARQ scheme, in case of performing retransmission by the ARQ scheme, previously data and retransmitted data are combined together and then reconstructed by FEC code. In accordance with a technique for combining the two kinds of data, the HARQ scheme is categorized into Chase combining and Incremental Redundancy. The Chase Combining, as shown in FIG. 5, is a scheme of raising a success rate of a receiver in receiving data in a manner that transmission data and retransmission data are combined together by a the receiver.
The Incremental Redundancy, as shown in FIG. 6, is a scheme of raising a reception success rate by lowering a code rate of data received by a receiver in a manner of transmitting a portion of coded data unused for a first transmission, unlike the Chase Combining, in case of a retransmission performed by a transmitter.
LDPC Code is explained as follows. Concepts of the LDPC Code are explained.
First, a linear code can be described as a generation matrix G or a check matrix H. The linear code is characterized in that a code is configured to satisfy HcT=0 for every codeword c. The currently noticeable LDPC code, which is a sort of the linear code, has been proposed first by Gallager in 1962. The LDPC code is characterized in that iterative decoding based on probability is possible in a manner that elements of a parity check matrix mostly consist of zeros and that the number of non-zero elements is set to a number smaller than a code length. In the first proposed LDPC code, a parity check matrix is defined non-systematic and is designed to have a uniformly small weight in rows and columns. Here, the weight means the number of 1s included in a column or row of a matrix.
Since density of non-zero elements in a parity check matrix H of LDPC code is low, it brings a low decoding complexity. Moreover, as decoding performance is better than those of conventional codes, LDPC Code has good performance approximating a theoretical limit of Shannon. Yet, LDPC Code has had difficulty in hardware implementation, attention has not been paid to LDPC Code over past 30 years. In the early 1980's, an iterative decoding method using graphs has been developed. So, various kinds of algorithms capable of decoding LDPC Code using this method have been developed. As a representative algorithm, there is a sum-product algorithm.
Features of LDPC code are explained as follows. The LDPC code has high error correction performance, which enables improvements in communication speed and size. The LDPC coding scheme can be combined with MIMO (multiple input multiple output) system to be applicable to high-speed wireless LAN capable of transmission at several hundreds Mbits/s, high-speed mobile communication having a data rate over 1 Mbits/s at 250 km/h, and optical communication over 40 Gbits/s. Owing to the high error correction performance of the LDPC Code, a quality of transmission is enhanced to enable quantization encrypted communication that reduces a count of retransmissions on a low-quality communication path. Owing to low complexity and outstanding loss compensation of the LDPC Code, a lost or damaged packet can be easily reconstructed, which enables contents having the same quality of TV to be transmitted via Internet or mobile communication. Owing to the wide application range and the large size of LDPC, it is now possible to implement 10 GBASE-T up to a range of 100 m, which was considered impossible, through the LDPC Code. Simultaneously, it is able to extend a transmission capacity of a single satellite transmitter of 36 MHz band up to 1.3 times increased, i.e., 80 Nbits/s.
A structured LDPC coding scheme is explained as follows.
First, a parity check matrix H is used to use LDPC Code. Most elements of the used matrix H consist of zeros and the rest consist of 1s. Since a size of the matrix H s over 105 bits, a large-size memory is required for representing the matrix H. The structured LDPC scheme is to represent elements of the matrix H used for LDPC encoding/decoding as a sub-block having a predetermined size as shown in FIG. 7. In IEEE802.16e, the sub-block is represented as a single integer index to reduce a size of memory required for storing the matrix H. The sub-block can include one of various matrixes. For instance, the sub-block can include a permutation matrix having a predetermined size.
If the structured LDPC scheme is employed, a single integer (i.e., index) is just stored in a specific memory instead of storing a matrix having a predetermined size with 1s and 0s therein. Hence, it is able to reduce a size of memory required for representing the matrix H.
For instance, if a size of codeword reflected on IEEE802.16e standard is 2,304 and if a code rate is ⅔, a model matrix used for LDPC encoding/decoding can be represented as FIG. 8. The model matrix means a parity check matrix consisting of at least one sub-block represented as a shift number that will be explained later. The model matrix can be expanded into a party check matrix by the following matrix. Hence, the meaning of executing encoding/decoding with a specific model matrix indicates that encoding/decoding is executed using a parity check matrix expanded from the corresponding model matrix.
The structure LDPC matrix, as shown in FIG. 8, can be represented as ‘−1’, ‘0’ and a positive number. If an index is ‘−1’, it indicates a zero matrix having a specific size. If an index is ‘0’, it indicates an identity matrix having a specific size. And, an index having a positive number except ‘−1 ’and ‘0’ indicates a shift number. If a sub-block is represented as an index ‘1’, the corresponding sub-block is configured by being shifted ‘1’ time in a specific direction from an identity matrix.
FIG. 9 is a diagram for a method of representing a matrix in accordance with the index, i.e., the shift number. When a specific parity check matrix is structured into a 4×4 matrix (i.e., sub-block), if the specific sub-block is represented as an index ‘3’, the sub-block becomes the matrix shown n FIG. 9.
A method of LDPC coding is explained as follows.
In general LDPC encoding, a generation matrix G is derived from a parity check matrix H and then information bits are encoded. In order to derive the generation matrix G, the parity check matrix H is configured into [PT:I] by Gaussian Reduction. Assuming that the number of the information bits is set to k and assuming that a size of encode codeword is set to n, the matrix P is a matrix of which number of rows is k and of which number of columns is (n−k). And, the matrix I is an identity matrix of which a row size if k and of which column size is k.
If the generation matrix G is represented as [PT:I], it becomes [I:P] matrix. If k-bit information bits to be encoded are represented as a matrix, they can be represented as a matrix x of which number of row is 1 and of which number of columns is k. In this case a codeword c can be represented as a following Equation.c=xG=[x:xP]  [Equation 1]
In Equation 1, ‘x’ indicates an information part or a systematic part and ‘xp’ indicates a parity part.
Meanwhile, in case that encoding is executed by Gaussian Reduction, a calculation amount is considerably large. So, instead of deriving the matrix G by designing a form of the matrix H into a special structure, the matrix H is directly encoded into the matrix G. In particular, if Equation 1 is multiplied by HT using a feature that a product of the matrix G and a transposed matrix HT of the matrix H is 0 (i.e., GHT=0), Equation 2 can be obtained. Hence, it is able to obtain a codeword c by adding a parity bit coinciding with Equation 2 behind an information bit (x).cHT=xGHT=[x:xP][PT:I]T=0  [Equation 2]
In a communication system, encoded data contains noise in the course of passing through the wireless channel shown in FIG. 1. And, a receiver has a data decoding process by the procedure shown in FIG. 10. A decoding block of the receiver finds information bits (x) from a received signal (c′) having noise added to an encoded codeword (c) using the feature of cHT=0. In particular, assuming that a received codeword is c′, a value of c′HT is calculated. If a corresponding result is 0, first k bits of c′ are decided as the information bits (x). If a value of c′HT is not 0, the information bits (x) are reconstructed by finding c′ that satisfies c′HT=0 using a decoding scheme such as sum-product algorithm through a graph and the like.
A code rate of LDPC code is explained as follows.
Generally, if a size of the information bits is k and if a size of a codeword actually transmitted is n, a code rate (R) can be represented as follows.R=k/n  [Equation 3]
If row and column sizes of the matrix H necessary for LDPC encoding/decoding are m and n, respectively, a code rate can be represented as follows.R=1−m/n  [Equation 4]
As mentioned in the foregoing description, the related art LDPC code performs encoding/decoding by the matrix H. So, a structure of the matrix H is very important. In particular, since performance of encoding/decoding is considerably affected by the structure of the matrix H, a design of the matrix H is important more than anything else.
In case of performing retransmission by the IR scheme, a code rate of an initial transmission should differ from that of a retransmission. In order to apply the different code rates, different model matrixes may be used. If so, there rises a problem that the IR scheme may not be supported. For instance, in case that a first model matrix used for an initial transmission differs from a second model matrix used after reception of NACK signal, a parity bit generated from the first model matrix is different from that generated from the second model matrix. Hence, a combined reception by a receiver is impossible.